package likou.bfs;


import java.util.*;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/28 21:48
 */
public class _127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int res = 1;
        Set<String> wordSet = new HashSet<>(wordList);//全部的单词
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return 0;
        }
        wordSet.remove(beginWord);

        Queue<String> existLeftQueue = new LinkedList<>();//当前左层
        existLeftQueue.offer(beginWord);

        Set<String> nowLeftSet = new HashSet<>();//当前左已经过
        nowLeftSet.add(beginWord);

        Queue<String> existRightQueue = new LinkedList<>();//当前右层
        existRightQueue.offer(endWord);

        Set<String> nowRightSet = new HashSet<>();//当前右已经过
        nowRightSet.add(endWord);

        while (!existLeftQueue.isEmpty()) {
            int n = existLeftQueue.size();
            for (int i = 0; i < n; i++) {
                String nowWord = existLeftQueue.poll();
                if (bfs(wordSet, nowLeftSet, nowRightSet, existLeftQueue, nowWord)) {
                    return res + 1;
                }
            }
            res++;
            n = existRightQueue.size();
            for (int i = 0; i < n; i++) {
                String nowWord = existLeftQueue.poll();
                if (bfs(wordSet, nowRightSet, nowLeftSet, existRightQueue, nowWord)) {
                    return res + 1;
                }
            }
            res++;
        }
        return 0;

    }

    private boolean bfs(Set<String> wordSet, Set<String> nowLeftSet, Set<String> nowRightSet, Queue<String> existQueue, String nowWord) {
        char[] chars = nowWord.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char k = 'a'; k <= 'z'; k++) {
                if (k == old) {
                    continue;
                }
                chars[i] = k;
                String nextWord = String.valueOf(chars);
                if (wordSet.contains(nextWord)) {
                    if (nowRightSet.contains(nextWord)) {
                        return true;
                    }
                    if (!nowLeftSet.contains(nextWord)) {
                        existQueue.offer(nextWord);

                        nowLeftSet.add(nextWord);
                    }

                }
            }
            chars[i] = old;
        }
        return false;
    }
}